//
// Created by 86138 on 2025/6/22.
//

#include "InsertSort.h"

namespace sweetcookie10_1 {

    void InsertSort(SqList &L) {
        int i, j;
        for (i = 2; i <= L.length; i++) {
            if (L.base[i].key < L.base[i - 1].key) { // 如果已经比最后一个已排序元素大或相等，就不用排序这个元素了
                L.base[0] = L.base[i]; // 复制为哨兵
                for (j = i - 1; L.base[0].key < L.base[j].key; j--) {
                    L.base[j + 1] = L.base[j]; // 记录后移
                }
                L.base[j + 1] = L.base[0]; // 插入到正确位置
            }
        }
    }

    void BInsertSort(SqList &L) {
        int i, j;
        for (i = 2; i <= L.length; i++) {
            if (L.base[i].key < L.base[i - 1].key) {
                L.base[0] = L.base[i];
                int low, high, mid;
                low = 1, high = i - 1;
                while (low <= high) {
                    mid = (low + high) / 2;
                    if (L.base[0].key < L.base[mid].key) {
                        high = mid - 1;
                    } else { // 这里和前面的折半查找条件有点不一样，不必考虑相等，而是大于等于
                        low = mid + 1;
                    }
                } // while结束，[high + 1]是插入位置
                for (j = i - 1; j >= high + 1; j--) {
                    L.base[j + 1] = L.base[j];
                }
                L.base[high + 1] = L.base[0];
            }
        }
    }

    void ShellInsert(SqList &L, int dk) {
        int i, j;
        for (i = dk + 1; i <= L.length; i++) {
            if (L.base[i].key < L.base[i - dk].key) {
                L.base[0] = L.base[i]; // base[0]只是暂存单元，不是哨兵
                for (j = i - dk; j > 0 && L.base[0].key < L.base[j].key;j -= dk) {
                    L.base[j + dk] = L.base[j];
                }
                L.base[j + dk] = L.base[0];
            }
        }
    }

    void ShellSort(SqList &L, int delta[], int t) {
        int k;
        for (k = 0; k < t; k++) {
            ShellInsert(L, delta[k]); // 一趟增量为delta[k]的直接插入排序
            printf("delta[%d]=%d, 第%d趟排序结果（仅输出关键字）：", k, delta[k], k + 1);
            Print1(L);
        }
    }

    void InputFromFile(FILE* f, RedType &c)
    { fscanf(f, "%d%d", &c.key, &c.otherinfo);
    }

    void Print(SqList L)
    { int i;
        for(i=1; i<=L.length; i++)
            printf("(%d, %d)", L.base[i].key, L.base[i].otherinfo);
        printf("\n");
    }

    void Print1(SqList L)
    { int i;
        for(i=1; i<=L.length; i++)
            printf("%d ", L.base[i].key);
        printf("\n");
    }
}

using namespace sweetcookie10_1;

//int main() {
//    system("chcp 65001");
//    FILE *f;
//    SqList m1, m2, m3, m4;
//    int i;
//    f = fopen("D:\\playground5\\qingdao-university\\10-sort\\f9-1.txt", "r");
//    fscanf(f, "%d", &m1.length);
//    for (i = 1; i <= m1.length; i++) {
//        InputFromFile(f, m1.base[i]);
//    }
//    fclose(f);
//    m4 = m3 = m2 = m1; // 数组会被正确复制，因为 C++ 的默认赋值操作（=）会对结构体进行逐成员复制
//
//    printf("排序前：\n");
//    Print(m1);
//    InsertSort(m1);
//    printf("直接插入排序后：\n");
//    Print(m1);
//    BInsertSort(m2);
//    printf("折半插入排序后：\n");
//    Print(m2);
//
//    return 0;
//}

//#define N 10
//#define T 3
//int main()
//{
//    system("chcp 65001");
//    RedType d[N]={{49, 1}, {38, 2}, {65, 3}, {97, 4}, {76, 5}, {13, 6},
//                  {27, 7}, {49, 8}, {55, 9}, {4, 10}};
//    SqList m;
//    int i, dt[T]={5, 3, 1};
//    for(i=0; i<N; i++)
//        m.base[i+1]=d[i];
//    m.length=N;
//    printf("希尔排序前：\n");
//    Print(m);
//    ShellSort(m, dt, T);
//    printf("希尔排序后：\n");
//    Print(m);
//    return 9;
//}